P2522 [HAOI2011]Problem b

显然,此题可用容斥化简:

i=abj=cd[gcd(i,j)=k]\sum_{i=a}^b\sum_{j=c}^d[gcd(i,j)=k]

i=1bj=1d[gcd(i,j)=k]i=1a1j=1d[gcd(i,j)=k]i=1bj=1c1[gcd(i,j)=k]+i=1a1j=1c1[gcd(i,j)=k]\Rightarrow\sum_{i=1}^b\sum_{j=1}^d[gcd(i,j)=k]-\sum_{i=1}^{a-1}\sum_{j=1}^d[gcd(i,j)=k]-\sum_{i=1}^b\sum_{j=1}^{c-1}[gcd(i,j)=k]+\sum_{i=1}^{a-1}\sum_{j=1}^{c-1}[gcd(i,j)=k]

对于每一部分,我们可以单独计算:

i=1nj=1m[gcd(i,j)=k]\sum_{i=1}^n\sum_{j=1}^m[gcd(i,j)=k]

i=1nkj=1mk[gcd(i,j)=1]\sum_{i=1}^{\lfloor \frac{n}{k} \rfloor }\sum_{j=1}^{\lfloor \frac{m}{k} \rfloor}[gcd(i,j)=1]

i=1nkj=1mkdgcd(i,j)μ(d)\sum_{i=1}^{\lfloor \frac{n}{k} \rfloor }\sum_{j=1}^{\lfloor \frac{m}{k} \rfloor}\sum_{d|gcd(i,j)}\mu(d)

d=1min(n,m)μ(d)i=1nkdj=1mkd\sum_{d=1}^{min(n,m)}\mu(d)\sum_{i=1}^{\lfloor \frac{n}{kd} \rfloor }\sum_{j=1}^{\lfloor \frac{m}{kd} \rfloor}

d=1min(n,m)μ(d)nkdmkd\sum_{d=1}^{min(n,m)}\mu(d)\lfloor \frac{n}{kd} \rfloor\lfloor \frac{m}{kd} \rfloor

可以用数论分块Θ(n )\Theta(\sqrt{n}~)解决,总复杂度为Θ(tn)\Theta(t\sqrt{n})

注意,这道题 #define int   long longdefine~int~~~long~long会见祖宗的,答案开long longlong ~long即可。

#include <cstdio>
#include <iostream>
using namespace std;

const int MAXN = 50000;
int n , a , b , c , d , f[ MAXN + 5 ];

int mu[ MAXN + 5 ] , prime[ MAXN + 5 ] , k;
bool vis[ MAXN + 5 ];
void sieve( ) {
	mu[ 1 ] = 1;
	for( int i = 2 ; i <= MAXN ; i ++ ) {
		if( !vis[ i ] ) {
			prime[ ++ k ] = i;
			mu[ i ] = -1;
		}
		for( int j = 1 ; j <= k && 1ll * i * prime[ j ] <= MAXN ; j ++ ) {
			vis[ i * prime[ j ] ] = 1;
			if( i % prime[ j ] == 0 ) break;
			mu[ i * prime[ j ] ] = -mu[ i ];
		}
	}
	for( int i = 1 ; i <= MAXN ; i ++ )
		f[ i ] = f[ i - 1 ] + mu[ i ];
}

long long solve( int n , int m ) {
	int d = min( n , m );
	long long Ans = 0;
	for( int l = 1 , r ; l <= d ; l = r + 1 ) {
		r = min( n / ( n / l ) , m / ( m / l ) );
		Ans = Ans + 1ll * ( f[ r ] - f[ l - 1 ] ) * ( n / k / l ) * ( m / k / l );
	}
	return Ans;
}
long long Get( ) {
	return solve( b , d ) - solve( a - 1 , d ) - solve( b , c - 1 ) + solve( a - 1 , c - 1 );
}

signed main( ) {
	sieve( ); 
	scanf("%d",&n);
	while( n -- ) {
		scanf("%d %d %d %d %d",&a,&b,&c,&d,&k);
		printf("%lld\n",Get( )); 
	} 
	return 0;
}